package binarysearchtree;

public class Solution {
   static TreeNode root;
   static TreeNode pre=null;
    /**
     * 插入一个元素
     * @param value 要插入的值
     * @return
     */
    public static boolean insert(int value) {
        //建立新结点
       TreeNode treeNode = new TreeNode(value);
        //判断根结点是否为空
        if(root==null){
            root=treeNode;
            return true;
        }
        //处理跟结点不为空的情况
       TreeNode cur=root;
        //对树进行遍历
      TreeNode prev=null;
        while(cur!=null){

            if(cur.val==value){
                return false;
            }
            //将当前结点进行保存
            prev=cur;
            //对值的大小进行比较
            if(value>cur.val){
                cur=cur.right;
            }
            else{
                cur=cur.left;
            }
        }
        if(prev.val>value){
            prev.left=treeNode;
        }
        else{
            prev.right=treeNode;
        }
        return true;
    }

    public static void main(String[] args) {
        int[]arr={10,6,14,4,8,12,16};
        for(int i=0;i< arr.length;++i){
            insert(arr[i]);
        }
        System.out.println(Convert(root));
    }
    public static TreeNode Convert(TreeNode pRootOfTree) {
        //判断树的有效性
        if(pRootOfTree==null){
            return null;
        }
        //遍历找到头结点
        TreeNode cur=pRootOfTree;
        while(cur.left!=null){
            cur=cur.left;
        }
        TreeNode head=cur;
        //将cur复原
        cur=pRootOfTree;
        //定义前驱结点
        TreeNode pre=null;
        //  遍历
        midOrder(cur,pre);
        return head;
    }
    public static void midOrder(TreeNode head,TreeNode pre){
        if(head==null){
            return;
        }
        midOrder(head.left,pre);
        //处理结点
        if(pre!=null){
            pre.right=head;
        }
        head.left=pre;
        pre=head;
        //处理右子树
        midOrder(head.right,pre);
    }
}